package main.leetcode.clockin.April;

/**
 * 42.接雨水
 *
 * <p>给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 *
 *
 * <p>示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day4 {
    public static void main(String[] args) {
        System.out.println(new day4().trap(new int[] {5, 5, 1, 7, 1, 1, 5, 2, 7, 6}));
    }
    // 暴力法
    //    public int trap(int[] height) {
    //        int leftMax, rightMax;
    //        int n = height.length;
    //        int res = 0;
    //        for (int i = 1; i < n; ++i) {
    //            leftMax = rightMax = 0;
    //            for (int j = i - 1; j >= 0; --j) {
    //                leftMax = Math.max(leftMax, height[j]);
    //            }
    //            if (leftMax < height[i]) continue;
    //            for (int k = i + 1; k < n; ++k) {
    //                rightMax = Math.max(rightMax, height[k]);
    //            }
    //            if (rightMax < height[i]) continue;
    //            res += Math.min(leftMax, rightMax) - height[i];
    //        }
    //        return res;
    //    }

    // 动态编程——事先遍历存储两边最大值
    //    public int trap(int[] height) {
    //        int n = height.length;
    //        if (n < 3) return 0;
    //        int tmp;
    //        int res = 0;
    //        int[] left = new int[n];
    //        int[] right = new int[n];
    //        left[0] = 0;
    //        right[n - 1] = 0;
    //        for (int i = 1, j = n - 2; i < n; ++i, --j) {
    //            left[i] = Math.max(left[i - 1], height[i - 1]);
    //            right[j] = Math.max(right[j + 1], height[j + 1]);
    //        }
    //        for (int i = 0; i < n; ++i) {
    //            res += (tmp = Math.min(left[i], right[i])) < height[i] ? 0 : tmp - height[i];
    //        }
    //        return res;
    //    }

    // 单调栈
    //    public int trap(int[] height) {
    //        int n = height.length;
    //        if (n < 3) return 0;
    //        int res = 0;
    //        int pop, h;
    //        Stack<Integer> stack = new Stack<>(); // stack里存的是雨水高度对应的下标值
    //        for (int i = 0; i < n; ++i) {
    //            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
    //                pop = stack.pop();
    //                if (stack.isEmpty()) break;
    //                h = Math.min(height[stack.peek()], height[i]); // 得到两根柱子中最短的高度
    //                res += (h - height[pop]) * (i - stack.peek() - 1);
    //            }
    //            stack.add(i);
    //        }
    //        return res;
    //    }

    // 双指针
    //    public int trap(int[] height) {
    //        int n = height.length;
    //        if (n < 3) return 0;
    //        int res = 0;
    //        int left = 0, right = n - 1;
    //        int leftMax = 0, rightMax = 0;
    //        while (left < right) {
    //            if (height[left] < height[right]) {
    //                if (height[left] >= leftMax) {
    //                    leftMax = height[left];
    //                } else {
    //                    res += leftMax - height[left];
    //                }
    //                ++left;
    //            } else {
    //                if (height[right] >= rightMax) {
    //                    rightMax = height[right];
    //                } else {
    //                    res += rightMax - height[right];
    //                }
    //                --right;
    //            }
    //        }
    //        return res;
    //    }

    // 双指针改版
    public int trap(int[] height) {
        int n = height.length;
        if (n < 3) return 0;
        int res = 0;
        int left = 0, right = n - 1;
        int leftMax = height[0], rightMax = height[right];
        // 如果left_max<right_max成立，那么它就知道自己能存多少水了
        // 无论右边将来会不会出现更大的right_max，都不影响这个结果
        while (left <= right) {
            if (leftMax <= rightMax) {
                res += Math.max(0, leftMax - height[left]);
                leftMax = Math.max(leftMax, height[left]);
                ++left;
            } else {
                res += Math.max(0, rightMax - height[right]);
                rightMax = Math.max(rightMax, height[right]);
                --right;
            }
        }
        return res;
    }
}
